//
//  main.swift
//  others
//
//  Created by lhc on 2024/8/17.
//

import Foundation

func main() {
    testTrie()
//    testUnionFind()
    testBSTree()
    testAVLTree()
    testRBTree()
}

func testTrie() {
    
    var check = true
    let string1 = "pen"
    let string2 = "penapple"
    
    let trie = Trie()
    trie.add(str: string1)
    trie.add(str: string1)
    
    
    if !trie.contain(str: string1) && trie.contain(str: string2) {
        check = false
    }
    
    trie.add(str: string2)
    
    if trie.getSize() != 2 {
        check = false
    }
    
    if !trie.contain(str: string1)
        && !trie.contain(str: string2)
        && !trie.isPrefix(string1) {
        check = false
    }
    
    
    if check {
        print("字典树 添加和查找没问题")
    }else {
        print("字典树 添加和查找有bug")
    }
}

func testUnionFind() {
    let size = 5000
    let uf1 = UnionFindLevel1(size: size)
    let uf2 = UnionFindLevel2(size: size)
    let uf3 = UnionFindLevel3(size: size)
    let uf4 = UnionFindLevel4(size: size)
    
    checkUF(uf1, name: "顺序表结构并查集")
    compareTime(uf: uf1, size: size, name: "顺序表结构并查集")
    
    checkUF(uf2, name: "自底向上指引并查集")
    compareTime(uf: uf2, size: size, name: "自底向上指引并查集")
    
    checkUF(uf3, name: "rank优化并查集")
    compareTime(uf: uf3, size: size, name: "rank优化并查集")
    
    checkUF(uf4, name: "路经压缩优化并查集")
    compareTime(uf: uf4, size: size, name: "路经压缩优化并查集")
}

func compareTime(uf: UnionFind, size: Int, name: String) {
    let startTime = Date().timeIntervalSince1970
    
    for _ in 0..<size {
        let a = Int.random(in: 0..<size)
        let b = Int.random(in: 0..<size)
        uf.unionElement(p: a, q: b)
    }
    
    for _ in 0..<size {
        let a = Int.random(in: 0..<size)
        let b = Int.random(in: 0..<size)
        let _ = uf.isConnected(p: a, q: b)
    }
    
    let endTime = Date().timeIntervalSince1970
    print("\(name) 耗时 \(TimeInterval(endTime - startTime).description) 秒")
}

func checkUF(_ uf: UnionFind, name: String) {
    var check = true
    uf.unionElement(p: 0, q: 4)
    uf.unionElement(p: 2, q: 0)
    if !uf.isConnected(p: 2, q: 4) || uf.isConnected(p: 0, q: 1) {
        check = false
    }
    uf.unionElement(p: 2, q: 1)
    if !uf.isConnected(p: 1, q: 4) {
        check = false
    }
    if check {
        print("\(name) 实现没问题")
    }else {
        print("\(name) 实现有bug")
    }
}

func testBSTree() {
    
    let bst = BSTree<Int, Int>()
    let temp = [5, 6, 1, 3, 4, 2]
    for i in temp {
        bst.add(key: i, value: i)
    }
    testBinaryTree(tree: bst, resultsArray: [1,2,3,4,5,6], treeName: "二分搜索树", message: "添加功能")
    bst.remove(key: 3)
    testBinaryTree(tree: bst, resultsArray: [1,2,4,5,6], treeName: "二分搜索树", message: "删除功能")
}

func testAVLTree() {
    let avl = AVLTree<Int, Int>()
    let temp = [5, 6, 1, 3, 4, 2]
    for i in temp {
        avl.add(key: i, value: i)
    }
    testBinaryTree(tree: avl, resultsArray: [1,2,3,4,5,6], treeName: "AVL树", message: "添加功能")
    
    let b1 = avl.isBalanceTree()
    
    avl.removeKey(3)
    testBinaryTree(tree: avl, resultsArray: [1,2,4,5,6], treeName: "AVL树", message: "删除功能")
    
    let b2 = avl.isBalanceTree()
    
    if b1 && b2 {
        print("实现的AVL树是平衡二叉树")
    }else {
        print("实现的AVL树是不平衡")
    }
}

func testRBTree() {
    let rbt = AVLTree<Int, Int>()
    let temp = [5, 6, 1, 3, 4, 2]
    for i in temp {
        rbt.add(key: i, value: i)
    }
    testBinaryTree(tree: rbt, resultsArray: [1,2,3,4,5,6], treeName: "红黑树", message: "添加功能")
    if rbt.isBalanceTree() {
        print("实现的红黑树是平衡二叉树")
    }else {
        print("实现的红黑树是不平衡")
    }
}


func testBinaryTree<T: Comparable, E>(tree: BinaryTree<T, E>, resultsArray: [T], treeName: String, message: String) {
    var inOrderList = [T]()
    tree.inOrder { key, value in
        inOrderList.append(key)
    }
    
    if resultsArray == inOrderList {
        print("\(treeName)的\(message) 无问题")
    }else {
        print("\(treeName)的\(message) 有bug")
    }
}


main()



